#pragma once

#include<new>
#include<cstddef>
#include<cstdlib>

namespace mytinystl
{
	union obj {          //避免内存浪费的union
		union obj *next; //指向下一个区块
		char client[1];  //储存本块内存的首地址
	};

	class Alloc
	{
	private:
		enum EAlign { ALIGN = 8 };                                            //将用户需求的内存大小调整到这个的倍数
		enum EMaxBytes { MAXBYTES = 128 };                                    //一块内存最多这么大，比这个还大的内存就调用一级配置器
		enum ENFreeLists { NFREELISTS = EMaxBytes::MAXBYTES / EAlign::ALIGN };//freelist数组的长度 = 16
		enum ENObjs { NOBJS = 20 };                                           //每次增加这么几块内存

	private:
		static obj* volatile free_list[ENFreeLists::NFREELISTS];

	private:
		static char* start_free;  //内存池起始地址
		static char* end_free;	  //内存池结束地址
		static size_t heap_size;  //内存池大小

	private:
		//把用户需要的内存大小上调至8的倍数
		inline size_t ROUND_UP(size_t bytes) {                               
			return (((bytes)+EAlign::ALIGN - 1) & (~EAlign::ALIGN - 1));
		}

		//找到这个需求对应大小的内存块所在的自由链表在freelist的位置，从0开始
		inline size_t FREELIST_INDEX(size_t bytes) {                         
			return(((bytes)+EAlign::ALIGN - 1) / EAlign::ALIGN - 1);
		}

		//当free list中空间不够，就给free list重新申请一块n bytes内存，返回分配出来的内存的首地址
		void* REFILL(size_t n) {      	
			size_t nobjs = 10;
			//CHUNK_ALLOC取得大小为 n bytes 的 nobj 个区块，返回指针指向区块的首地址
			char* chunk = CHUNK_ALLOC(n, nobjs);  //向内存池申请，这里nobjs可能已经不是10了，chunk alloc能分几块分几块
			obj * my_free_list;
			obj * result;
			obj * cur, * next;
			if (nobjs == 1) {
				// 如果只有一个区块，就把这个区块返回给调用者，free list 没有增加新节点
				return chunk;
			}
			//否则把一个区块给用户，剩下的挂链表
			my_free_list = free_list[FREELIST_INDEX(n)];
			result = (obj *) chunk;//把分配出来的第一个给用户
			my_free_list = next = (obj*)(chunk + n);//剩下的挂链表
			for (int i = 1;; i++) {
				cur = next;
				next = (obj*)(char*)next + n;//next向后移一个块
				if (nobjs - 1 == i) {
					//剩下要挂链表的都安排完了
					cur->next = nullptr;
				}
				else
				{
					cur->next = next;
				}
			}
			return result;
		}

		//从内存池中取出内存给free list用
		char* CHUNK_ALLOC(size_t size, size_t &nobjs) {
			char * result;
			size_t need_memory = size * nobjs;
			size_t poll_memory = end_free - start_free;

			if (poll_memory >= need_memory) {
				//内存池完全够
				result = start_free;
				start_free += need_memory;//返回内存池首地址作为分配出去的结果，余下的往后移就行了
				return result;
			}
			else if (poll_memory >= size) {
				//内存池不完全够，但够分一个及以上的块
				nobjs = poll_memory / size;//能分几个
				need_memory = size * nobjs;//分了多大
				result = start_free;
				start_free += need_memory;
				return result;
			}
			else {
				//内存池连一个块都没有
				size_t memory_to_get = 2 * need_memory + ROUND_UP(heap_size >> 4);
				if (poll_memory > 0) {
					//内存池一个块也不够分，但还有一点零头，把这些零头分给合适的free list
					obj* my_free_list = free_list[FREELIST_INDEX(poll_memory)];
					((obj*)start_free)->next = my_free_list;
					my_free_list = (obj*)start_free;

				}
				//从这里开始内存池真的一点也没了
				start_free = (char*)std::malloc(memory_to_get);//配置heap
				if (0 == start_free) {
					//malloc失败
					obj* my_free_list, *p;
					for (size_t i = size; i <= EMaxBytes::MAXBYTES; i += ROUND_UP(i)) {
						//8 16 28 32 ... 128 循环
						my_free_list = free_list[FREELIST_INDEX(i)];//在freelist[i]上搜索
						p = my_free_list;
						if (p) {
							//这个free list还有没用的内存
							my_free_list = p->next;//这块内存被放进内存池
							start_free = (char*)p;//修改内存池起点
							end_free = start_free + i;//修改内存池终点
							return CHUNK_ALLOC(size, nobjs);//修正nobjs
						}
					}
					//循环完还是没return，说明free list上也没有空内存，到处都没内存了
					end_free = nullptr;
					throw std::bad_alloc();
				}
				heap_size += memory_to_get;
				return CHUNK_ALLOC(size, nobjs);
			}
		}

	public:
		//一二级分配器，给用户分配 n bytes 大小的空间
		inline void* allocate(size_t n) {        
			obj* my_free_list;
			obj* result_list;

			if (n > (size_t)EMaxBytes::MAXBYTES) {
				//大于规定字节调用第一级分配器
				return std::malloc(n);
			}
			else
			{
				my_free_list = free_list[FREELIST_INDEX(n)];//my free list指向16个块中负责这个大小的那块
				result_list = my_free_list;//试图把第一个分给用户
				if (result_list == nullptr) {
					void* refill = REFILL(ROUND_UP(n));//free list里没有空的了，refill
					return refill;
				}
				my_free_list = result_list->next;//result已经分给用户了，剩下的挂链表
				return result_list;
			}
		}

		//释放p指向的大小为n的用户空间
		inline void deallocate(void *p, size_t n) {  
			if (n > (size_t)EMaxBytes::MAXBYTES) {
				//大于规定大小就调第一级分配器
				std::free(p);
				return;
			}
			else
			{
				obj* q =reinterpret_cast <obj*> (p);//q也指向给用户的那个空间
				obj* my_free_list;
				my_free_list = free_list[FREELIST_INDEX(n)];//找到应该放回哪
				q->next = my_free_list;//把要回收的区块和目前空闲的块接上
				my_free_list = q;//并把新回来的块设为第一个块
			}
		}

		inline void *reallocate(void *p, size_t old_size, size_t new_size) {
			deallocate(p, old_size);
			p = allocate(new_size);
			return p;
		}

	};

	//静态变量初始化
	obj* volatile Alloc::free_list[ENFreeLists::NFREELISTS] = {
		nullptr,nullptr,nullptr,nullptr,
		nullptr,nullptr,nullptr,nullptr,
		nullptr,nullptr,nullptr,nullptr,
		nullptr,nullptr,nullptr,nullptr
	};

	char*  Alloc::start_free = nullptr;   //内存池起始地址
	char*  Alloc::end_free   = nullptr;   //内存池结束地址
	size_t Alloc::heap_size  = 0;         //内存池大小

}